package knapsack.strategies;

import java.util.Arrays;

import knapsack.core.KnapsackInstance;
import knapsack.core.KnapsackStrategy;

/**
 * This class represents dynamic programming approach for knapsack problem.
 * 
 * @author vasek
 *
 */
public final class DynamicProgramming implements KnapsackStrategy {
	
	private final KnapsackInstance instance;
	private final int[] weights;
	private final int[] costs;
	private final int[][] table;
	private int expandedStates = 0;
	
	/**
	 * Constructor.
	 * 
	 * @param instance which is being solved
	 */
	public DynamicProgramming(KnapsackInstance instance) {
		super();
		this.instance = instance;		
		this.weights = instance.getWeights();		
		this.costs = instance.getCosts();		
		this.table = new int[instance.getCount() + 1][instance.getCapacity() + 1];
	}

	@Override
	public void run() {
		for (int w = 0; w <= instance.getCapacity(); w++) {
			table[0][w] = 0;
		}
		
		for (int i = 1; i <= instance.getCount(); i++) {
			table[i][0] = 0;
		}
		
		for (int i = 1, index = 0; i <= instance.getCount(); i++, index++) {
			for (int w = 0; w <= instance.getCapacity(); w++) {
				expandedStates++;
				if (weights[index] <= w) {
					if ((costs[index] + table[i - 1][w - weights[index]]) > table[i - 1][w]) {
						table[i][w] = costs[index] + table[i - 1][w - weights[index]];	
					} else {
						table[i][w] = table[i - 1][w];
					}
				} else {
					table[i][w] = table[i - 1][w];
				}
			}
		}
	}

	@Override
	public int getKnapsackCost() {
		final int w = table[0].length - 1;
		final int n = table.length - 1;
		
		return table[n][w];		
	}

	@Override
	public int[] getKnapsackConfiguration() {
		return null;
	}

	@Override
	public KnapsackInstance getInstance() {
		return instance;
	}

	@Override
	public String toString() {
		final StringBuilder sb = new StringBuilder();
		
		for (int row = 0; row <= instance.getCount(); row++) {
			sb.append(Arrays.toString(table[row]));
			sb.append("\n");
		}
		
		return sb.toString();
	}

	@Override
	public int getNumberOfStatesExpanded() {
		return expandedStates;
	}

}
